Search for: All records

Given a locally flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on the plane) with a mountain-valley (MV) assignment $$\mu:E\to\{-1,1\}$$ indicating which creases in $$E$$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $$F$$ of $$G$$ to create a new MV assignment $$\mu_F$$ which equals $$\mu$$ except for all creases $$e$$ bordering $$F$$, where we have $$\mu_F(e)=-\mu(e)$$. In this paper we explore the configuration space of face flips that preserve local flat-foldability of the MV assignment for a variety of crease patterns $$G$$ that are tilings of the plane. We prove examples where $$\mu_F$$ results in a MV assignment that is either never, sometimes, or always locally flat-foldable, for various choices of $$F$$. We also consider the problem of finding, given two locally flat-foldable MV assignments $$\mu_1$$ and $$\mu_2$$ of a given crease pattern $$G$$, a minimal sequence of face flips to turn $$\mu_1$$ into $$\mu_2$$. We find polynomial-time algorithms for this in the cases where $$G$$ is either a square grid or the Miura-ori, and show that this problem is NP-complete in the case where $$G$$ is the triangle lattice. 

A Stick graph is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments lie on a “ground line,” a line with slope −1. It is an open question to decide in polynomial time whether a given bipartite graph G with bipartition A∪B has a Stick representation where the vertices in A and B correspond to horizontal and vertical segments, respectively. We prove that G has a Stick representation if and only if there are orderings of A and B such that G’s bipartite adjacency matrix with rows A and columns B excludes three small ‘forbidden’ submatrices. This is similar to characterizations for other classes of bipartite intersection graphs. We present an algorithm to test whether given orderings of A and B permit a Stick representation respecting those orderings, and to find such a representation if it exists. The algorithm runs in time linear in the size of the adjacency matrix. For the case when only the ordering of A is given, we present an O(|AB}^3)-time algorithm.